package hw;

import java.util.*;

public class FiberOpticInstallation {
    // 定义一个类来表示坐标点和距离
    static class Point {
        int x, y, distance;
        Point(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }

    // 定义方向：右、左、下、上
    private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    // 计算最短路径的主函数
    public static int shortestPath(int m, int n, int[] start, int[] target, List<int[]> obstacles) {
        boolean[][] visited = new boolean[m][n];
        for (int[] obstacle : obstacles) {
            visited[obstacle[0]][obstacle[1]] = true; // 标记障碍物
        }

        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(start[0], start[1], 0)); // 从起点开始
        visited[start[0]][start[1]] = true;

        // 广度优先搜索（BFS）算法
        while (!queue.isEmpty()) {
            Point current = queue.poll();

            // 检查是否到达目标位置
            if (current.x == target[0] && current.y == target[1]) {
                return current.distance;
            }

            // 探索所有可能的方向
            for (int[] dir : DIRECTIONS) {
                int newX = current.x + dir[0];
                int newY = current.y + dir[1];

                // 检查新位置是否在范围内并且未被访问过
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
                    queue.add(new Point(newX, newY, current.distance + 1));
                    visited[newX][newY] = true;
                }
            }
        }

        // 如果没有找到路径，则返回 -1
        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入矩阵宽度 m 和高度 n
        System.out.println("请输入矩阵的宽度（m）和高度（n）：");
        int m = scanner.nextInt();
        int n = scanner.nextInt();

        // 输入起点坐标
        System.out.println("请输入起点坐标（a1, a2）：");
        int[] start = {scanner.nextInt(), scanner.nextInt()};

        // 输入终点坐标
        System.out.println("请输入目标坐标（b1, b2）：");
        int[] target = {scanner.nextInt(), scanner.nextInt()};

        // 输入障碍物的数量
        System.out.println("请输入障碍物的数量：");
        int k = scanner.nextInt();

        // 输入每个障碍物的坐标
        List<int[]> obstacles = new ArrayList<>();
        System.out.println("请输入每个障碍物的坐标：");
        for (int i = 0; i < k; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            obstacles.add(new int[]{x, y});
        }

        // 计算最短路径
        int result = shortestPath(m, n, start, target, obstacles);
        System.out.println( result);
    }
}
